package com.zp.self.module.level_4_算法练习.算法.位图;

import org.junit.Test;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_128_最长连续序列 {
    @Test
    public void main() {

        System.out.println(longestConsecutive(new int[]{100,4,200,1,3,2}));
    }

    /**
    题目：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

     示例 1：
     输入：nums = [100,4,200,1,3,2]
     输出：4
     解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

     示例 2：
     输入：nums = [0,3,7,2,5,8,4,6,0,1]
     输出：9

    分析：【PR 💔💔💔】
       1.集合存储这个元素：当遍历到一个元素时，寻找 nums[i]+1 ,nums[i]-1 是否存在于集合中
                           注意：避免重复累积，应该先判断是发在集合中
                           递归的寻找，找之前删除自己
                        --执行用时：22 ms, 在所有 Java 提交中击败了45.32%的用户
                        --时长：超过30分钟

       大神：用set存储元素，再遍历数组时 删除掉set中的元素。遍历转嫁给了数组，让集合来删除  --妙啊
                        避免了重复去判断元素的左右点。
                        避免了过多的内存开销，相比我的Map存储
                       --执行用时：15 ms, 在所有 Java 提交中击败了58.81%的用户， 此时已经是最优的了，因为测试案例的原因 sort的O(n*logn) 会更快一点

    边界值 & 注意点：
       1.
     **/
    public int longestConsecutive(int[] nums) {
        //2.大神：用set存储元素，再遍历数组时 删除掉set中的元素。遍历转嫁给了数组，让集合来删除  --妙啊
        int max = 0;
        Set<Integer> set =  new HashSet<>();
        for (int num : nums)
            set.add(num);
        for (int num : nums) {
            if(!set.remove(num)) continue;
            int size = 1,pro=num-1,next=num+1;
            while (set.remove(pro--)){   //改递归为迭代
                size++;
            }
            while (set.remove(next++)){
                size++;
            }
            max = Math.max(max, size);
        }
        return max;
    }

    //1.集合存储这个元素：当遍历到一个元素时
    public int longestConsecutive2(int[] nums) {
        int max = 0, index = 0;
        Map<Integer, Integer> numbIndexMap = new HashMap<>();
        for (int num : nums) {
            if (!numbIndexMap.containsKey(num))
                numbIndexMap.put(num, index++);
        }
        boolean[] use = new boolean[numbIndexMap.size()];//标记下标是否被使用，
        numbIndexMap.keySet().iterator();
        for (Map.Entry<Integer, Integer> entry : numbIndexMap.entrySet()) {
            if (use[entry.getValue()]) continue;
            use[entry.getValue()] = true;
            int size = 1, pro = entry.getKey() - 1, next = entry.getKey() + 1;
            while (numbIndexMap.containsKey(pro)) {   //改递归为迭代
                use[numbIndexMap.remove(pro--)] = true;
                size++;
            }
            while (numbIndexMap.containsKey(next)) {
                use[numbIndexMap.remove(next++)] = true;
                size++;
            }
            max = Math.max(max, size);
        }
        return max;
    }
}
